Featured Blog | This community-written post highlights the best of what the game industry has to offer. Read more like it on the Game Developer Blogs.
Procedural Dungeon Generation Algorithm
This post explains a technique for generating randomized dungeons that was first described by the developer of Tiny Keep. I'll go over it in a little more detail than the steps in the original post.
This post explains a technique for generating randomized dungeons that was first described by TinyKeepDev here. I'll go over it in a little more detail than the steps in the original post. The general way the algorithm works is this:
Generate Rooms
First you wanna generate some rooms with some width and height that are placed randomly inside a circle. TKdev's algorithm used the normal distribution for generating room sizes and I think that this is generally a good idea as it gives you more parameters to play with. Picking different ratios between width/height mean and standard deviation will generally result in different looking dungeons.
One function you might need to do this is getRandomPointInCircle:
function getRandomPointInCircle(radius) local t = 2*math.pi*math.random() local u = math.random()+math.random() local r = nil if u > 1 then r = 2-u else r = u end return radius*r*math.cos(t), radius*r*math.sin(t) end
You can get more info on how that works exactly here. And after that you should be able to do something like this:
One very important thing that you have to consider is that since you're (at least conceptually) dealing with a grid of tiles you have to snap everything to that same grid. In the gif above the tile size is 4 pixels, meaning that all room positions and sizes are multiples of 4. To do this I wrap position and width/height assignments in a function that rounds the number to the tile size:
function roundm(n, m) return math.floor(((n + m - 1)/m))*m end -- Now we can change the returned value from getRandomPointInCircle to: function getRandomPointInCircle(radius) ... return roundm(radius*r*math.cos(t), tile_size), roundm(radius*r*math.sin(t), tile_size) end
Separate Rooms
Now we can move on to the separation part. There's a lot of rooms mashed together in one place and they should not be overlapping somehow. TKdev used the separation steering behavior to do this but I found that it's much easier to just use a physics engine. After you've added all rooms, simply add solid physics bodies to match each room's position and then just run the simulation until all bodies go back to sleep. In the gif I'm running the simulation normally but when you're doing this between levels you can advance the physics simulation faster.
The physics bodies themselves are not tied to the tile grid in any way, but when setting the room's position you wrap it with the roundm call and then you get rooms that are not overlapping with each other and that also respect the tile grid. The gif below shows this in action as the blue outlines are the physics bodies and there's always a slight mismatch between them and the rooms since their position is always being rounded:
One issue that might come up is when you want to have rooms that are skewed horizontally or vertically. For instance, consider the game I'm working on: